home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8219 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: stc06.ctd.ornl.gov!msr!kennel
  2. From: kennel@msr.epm.ornl.gov (Matt Kennel)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Followup-To: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  6. Date: 15 Feb 1996 20:46:45 GMT
  7. Organization: Oak Ridge National Lab, Oak Ridge, TN
  8. Message-ID: <4g063l$a3l@stc06.ctd.ornl.gov>
  9. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv74c$chq@gatekeeper.alcatel.no> <93bb.5.00122006@eng.cam.ac.uk>
  10. NNTP-Posting-Host: msr.epm.ornl.gov
  11. X-Newsreader: TIN [version 1.2 PL2]
  12.  
  13. To follow up on my last post, here is a solution programmed in MATLAB.
  14.  
  15. The algorithm is O(1) in space (no arrays needed) and O(n) in time.
  16.  
  17. The answer is that the last digit of 1000! is '2', followed by
  18. 249 zeros. 
  19.  
  20. The last digit of '10000!' is '8' followed by 2499 zeroes.
  21.  
  22. You can use this algorithm to find the last non-zero digit of any
  23. factorized large number. 
  24.  
  25. cheers
  26. matt
  27. kennel@msr.epm.ornl.gov
  28.     (hire me for big $$$? ;-) )
  29. /* My views are not those of the U.S. Department of Energy.
  30.    If you want their views you really have to go to war. */
  31.  
  32. function [res] = last_digit_of_n_fact(n)
  33. %%
  34. %% Find the last non-zero digit of n!
  35. %%
  36.  
  37. n2s=0;  %% pull out all factors of 2
  38. n5s=0;  %% all factors of 5
  39.  
  40. digit=1;
  41.  
  42. for i = 2:n,
  43.    [f,n2] = powers_of_p(i,2);
  44.    n2s = n2s+n2;
  45.    [g,n5] = powers_of_p(f,5);
  46.    n5s = n5s+n5;
  47.  
  48.    digit = rem(digit*g,10);  %% remainder mod 10
  49. end
  50.  
  51. %% collect 2s and 5s up into 10s, and ignore them.
  52. %% count the remaining 2's. 
  53.  
  54. if n2s > n5s
  55.    xtra2s = n2s-n5s;
  56.    for i = 1:xtra2s,
  57.      digit = rem(digit*2,10);  % gotta be a better theorem here.
  58.    end;
  59. elseif n5s > n2s  %% not very likely, kemosabe
  60.    xtra5s = n5s-n2s;
  61.    for i = 1:xtra5s,
  62.      digit = rem(digit*5,10);
  63.    end;
  64. end;
  65. res = digit;  %% the answer
  66. n10s = min(n2s,n5s)
  67. %% how many zeros at the end of 'n!'. 
  68. end;
  69.  
  70.  
  71.  
  72.  
  73. function [f, p2] = powers_of_p(n,p)
  74. %%
  75. %% Factorize 'n' into f*p^(p2)
  76. %%
  77.     if rem(n,p) == 0
  78.     [f,q] = powers_of_p(n/p,p);
  79.     p2 = q+1;
  80.     else
  81.     p2 = 0;
  82.     f = n;
  83.     end
  84. end
  85.  
  86.  
  87.  
  88.  
  89.